1. Technical Field
The present invention is related generally to an improved data processing system and, more particularly, to an improved first in last out data structure within a memory array.
2. Description of Related Art
A stack or First In Last Out (FILO) data structure is used in many computer applications. Often multiple stacks are needed in a single application and they are added as needed, because initially it is not known how many stacks will be needed. Memory in computer systems is commonly arranged as a linear array, with an application having some segment of this linear array that it will use to place multiple stacks. The way stacks are traditionally implemented is with a base and head pointer.
In a typical case, two stacks are placed at opposite ends of the memory array. One stack grows to the right and the other stack grows to the left. Each stack may grow until it hits the opposite stack coming from the opposite direction (which is referred to as a collision).
The arrangement with two stack growing toward one another from opposite ends of the array is efficient if both the stacks grow at the same rate. That is, all memory within the memory array will be consumed before a collision. However, if a third stack is needed, a problem may arise. If all three stacks grow at the same rate, the third stack grows in one direction, and the third stack is placed in the middle of the first two stacks, then the third stack will tend to collide with one of the other two stacks, before the other of the other two stacks has used all its space. The third stack could be offset in location from the center in an effort to anticipate this problem, but if the three stacks do not grow at the same rate, then the selected offset location of the third stack may not help.
In one of the related applications, these problems are addressed by one or more bidirectionally growing stacks. In another of the related applications, these problems are further addressed in stacks which are split into more than one part. Both of these inventions are useful for addressing the problems, as described, which arise in managing the space in a linear memory array, including allocation of the space. However, a need exists for a method or apparatus to manage memory having other features, which relate to aspects of these problems in a different way, and which may provide even greater adaptability in certain circumstances, particularly circumstances involving uncertain variation in growth rate of stacks.
The present invention addresses this need as follows. A storage area, with a first and second end, is provided for storing data elements. The data elements are stored in a first stack, also having a first and second end. Space in the storage area for the first stack includes a first space proximate the first end of the first stack, and a second space proximate the second end of the first stack. The storing of one of the data elements in the first stack includes selecting between storing in the first space or the second space, responsive to the relative sizes of the two spaces.
In another aspect, data elements are stored in the storage area in a second stack. Space available in the storage area for data elements of the second stack includes the above mentioned first and second spaces, that is, the space proximate the first end of the first stack, and the space proximate the second end of the first stack. Storing in the second stack includes selecting between storing in the first or second space, responsive to the relative sizes of the two spaces.